/*
 *  Copyright 2009 Advanced Industrial Science and Technology (AIST).
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

/*! \file
 *  \brief
 */

// thrust, includes
#include <thrust/random.h>
#include <thrust/for_each.h>
#include <thrust/sort.h>
#include <thrust/unique.h>

#include <thrust/graph/detail/adjacency_list.inl>

// stl, includes
#include <iostream>

namespace thrust {

namespace detail {

template <typename T>
__host__ __device__
void swap( T& x, T& y)
{
  T tmp =x;
  x =y;
  y =tmp;
}

// Robert Jenkins' 32 bit integer hash function
__host__ __device__
unsigned int hash(unsigned int a)
{
  a = (a+0x7ed55d16) + (a<<12);
  a = (a^0xc761c23c) ^ (a>>19);
  a = (a+0x165667b1) + (a<<5);
  a = (a+0xd3a2646c) ^ (a<<9);
  a = (a+0xfd7046c5) + (a<<3);
  a = (a^0xb55a4f09) ^ (a>>16);
  return a;
}

} // end namespace detail


template <typename RandNumGen>
struct edge_generator {

  __host__
  edge_generator( unsigned int max, bool self_edges, unsigned int seed)
    : m_max(max)
    , m_self_edges(self_edges)
    , m_seed(seed)
    , m_count(0)
    , m_local_loop(0) {}
  
  __host__
  void set_loop_count( unsigned int loop_count)
  {
    m_count =loop_count;
  }

  template <typename edge_descriptor>
  __device__
  void operator()( edge_descriptor& e)
  {
    typedef typename edge_descriptor::directed_category directed_category;
    operator()( e, directed_category());
  }
  
  template <typename edge_descriptor>
  __device__
  void operator()( edge_descriptor& e, undirected_tag)
  {
    unsigned int tid =blockDim.x * blockIdx.x + threadIdx.x;
    unsigned int seed =detail::hash( m_seed + tid + m_local_loop);
    m_gen.seed( seed + m_count);
    m_gen.discard( tid);

    thrust::uniform_int_distribution<unsigned int> u( 0, m_max-1);
    
    e.m_source =u( m_gen);
    e.m_target =u( m_gen);
      
    if( e.m_source >e.m_target)
      detail::swap( e.m_source, e.m_target);

    if( !m_self_edges){
      while( e.m_target ==e.m_source)
        e.m_target =u( m_gen);
    }
    m_local_loop++;
  }
  
  template <typename edge_descriptor>
  __device__
  void operator()( edge_descriptor& e, directed_tag)
  {
    unsigned int tid =blockDim.x * blockIdx.x + threadIdx.x;
    unsigned int seed =detail::hash( m_seed + tid + m_local_loop);
    m_gen.seed( seed + m_count);
    m_gen.discard( tid);
    
    thrust::uniform_int_distribution<unsigned int> u( 0, m_max-1);
    
    e.m_source =u( m_gen);
    e.m_target =u( m_gen);
    
    if( !m_self_edges){
      while( e.m_target ==e.m_source)
        e.m_target =u( m_gen);
    }
    m_local_loop++;
  }

private:
  bool m_self_edges;
  unsigned int m_seed;
  unsigned int m_max;
  unsigned int m_count;
  unsigned int m_local_loop;
  RandNumGen m_gen;
};

template <typename Edge, typename Vertex>
struct extract_target
{
  __device__
  Vertex
  operator()( const Edge& e)
  {
    return e.m_target;
  }
};

template <typename Edge, typename Vertex>
struct extract_source
{
  __device__
  Vertex
  operator()( const Edge& e)
  {
    return e.m_source;
  }
};

template <typename RandNumGen,typename Graph>
void
generate_random_graph( Graph& g
                       , typename graph_traits<Graph>::vertices_size_type V
                       , typename graph_traits<Graph>::edges_size_type    E
                       , bool allow_parallel
                       , bool self_edges
                       , unsigned int seed
                       )
{
  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
  typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
  typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
  typedef typename device_vector<edge_descriptor>::iterator Iter;

  edge_iterator first, last;
  first =g.m_out_edges.begin();
  last  =g.m_out_edges.end();
  
  edge_generator<RandNumGen> generator( V, self_edges, seed);
  
  thrust::detail::raw_cuda_device_buffer<vertex_descriptor> keys( E);
  
  unsigned int loop =0;
  edge_iterator iter =first;
  while( iter !=last){
    
    generator.set_loop_count( ++loop);

    thrust::for_each( iter, last, generator);
    
#ifdef USE_MERGE_SORT
    thrust::sort( first,
                  last, 
                  thrust::detail::less_edge_source<edge_descriptor>());
#else
    thrust::transform( first, last, keys.begin(), 
                       extract_target<edge_descriptor,vertex_descriptor>());
    thrust::stable_sort_by_key( keys.begin(), keys.end(), first);
    
    thrust::transform( first, last, keys.begin(),
                       extract_source<edge_descriptor,vertex_descriptor>());
    thrust::stable_sort_by_key( keys.begin(), keys.end(), first);
#endif
    
    if( allow_parallel){
      iter =last;
    }
    else{
      iter =thrust::unique( first, 
                            last, 
                            thrust::detail::equal_edge<edge_descriptor>());
    }
    
    g.m_num_out_edges =iter - first;
    
#ifdef DEBUG
    std::cout <<"num_edges: " <<g.m_num_out_edges <<std::endl;
#endif
    
  }
  
  thrust::detail::reconstruct( g, V, E);
  
  // edge property;
  g.reassign_edge_property();
}
  
} // end namespace thrust
